#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include <limits.h>
using namespace std;


//1. 3sum
vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > ans;

    if (num.size() < 3) return ans;

    sort(num.begin(), num.end());
    for (int i = 0; i < num.size() -2; i++) {
        int need = 0 - num[i];
	for (int j = i+1, k = num.size()-1; j < k; ) {
	    if (num[j] + num[k] < need) {
		j++;
	    } else if (num[j] + num[k] > need) {
		k--;
	    } else {
		vector<int> tmp;
		tmp.push_back(num[i]);
		tmp.push_back(num[j]);
		tmp.push_back(num[k]);
		ans.push_back(tmp);
		j++;
		k--;
	    }
	}
    }
    return ans;
}
//bug fix it 
vector<vector<int> > threeSum_fix(vector<int> &num) {
    set<vector<int> > ans;
    vector<vector<int> > rtn;

    if (num.size() < 3) return rtn;

    sort(num.begin(), num.end());
    for (int i = 0; i < num.size() -2; i++) {
        int need = 0 - num[i];
        for (int j = i+1, k = num.size()-1; j < k; ) { 
            if (num[j] + num[k] < need) {
                j++;
            } else if (num[j] + num[k] > need) {
                k--;
            } else {
                vector<int> tmp;
                tmp.push_back(num[i]);
                tmp.push_back(num[j]);
                tmp.push_back(num[k]);
                if (ans.count(tmp) == 0) {
                    rtn.push_back(tmp);
                    ans.insert(tmp);
                }
                j++;
                k--;
            }   
        }   
    }   
    return rtn;
}

//3sum cloest
    int threeSumClosest(vector<int> &num, int target) {
	int ans = 0;
	if (num.size() < 3) return ans;
	sort(num.begin(), num.end());
	//BUG : need to init ans to be this
	ans = num[0] + num[1] + num[2];    
	for (int i = 0; i < num.size()-2; i++) {
	    for (int j = i+1, k = num.size()-1; j < k; ){
		if (abs(num[i] + num[j] + num[k] - target) < abs(ans-target))
		    ans = num[i] + num[j] + num[k];

		if (num[i] + num[j] + num[k] == target) {
		    return target;
		} else if (num[i] + num[j] + num[k] > target) {
		    k--;
		} else {
		    j++;
		}
	    }
	}
	return ans;        
    }


//four sum 
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > ans;
	set<vector<int> > mySet;
	if (num.size() < 4) return ans;
	sort(num.begin(), num.end());
	for (int i = 0; i < num.size() - 3; i++) {
	    for (int j = i+1; j < num.size() - 2; j++) {
		int need = target - num[i] - num[j];
		for (int k = j+1, l = num.size()-1; k < l; ) {
		    if (num[k] + num[l] > need) {
			l--;
		    } else if (num[k] + num[l] < need) {
			k++;
		    } else {
			vector<int> tmp;
			tmp.push_back(num[i]);
			tmp.push_back(num[j]);
			tmp.push_back(num[k]);
			tmp.push_back(num[l]);
			if (mySet.count(tmp) == 0) {
			    ans.push_back(tmp);
			    mySet.insert(tmp);
			}
			k++;
			l--;
		    }
		}
	    }
	}
	return ans;
    }


//5 add binary
    string addBinary(string a, string b) {
	string ans;
        int carry = 0;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	for (int i = 0; i < a.size() || i < b.size(); i++) {
	    int a1 = i >= a.size() ? 0 :a[i] - '0';
	    int b1 = i >= b.size() ? 0 :b[i] - '0';
	    int sum = a1 + b1 + carry;
	    carry = sum/2;
	    sum = sum%2;
	    ans += sum + '0';
	}
	if (carry)
	    ans += '1';
	reverse(ans.begin(), ans.end());
	return ans;
    }

 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

//6 add two numbers
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
	ListNode dummy(0);
	ListNode *head = &dummy;
	int carry = 0;
	while(l1 || l2) {
	   int a = l1 ? l1->val : 0;
	   int b = l2 ? l2->val : 0;
	   int sum = a + b + carry;
	   carry = sum/10;
	   sum = sum%10;
	   head->next = new ListNode(sum);
	   head = head->next;
	   // bug again. check the pointer
	   if (l1) l1 = l1->next;
	   if (l2) l2 = l2->next;
	}
        if (carry)
            head->next = new ListNode(1);
	ListNode *cur = dummy.next;

	while(cur) {
	    cout << cur->val << " ";
	    cur = cur->next;
	}
	
        return dummy.next;
    }

//7 anagrams
    vector<string> anagrams(vector<string> &strs) {
        vector<string> ans;
	map<string, vector<string> > mp;
	for (int i = 0; i < strs.size(); i++) {
	    string hash = strs[i];
	    sort(hash.begin(), hash.end());
	    if (mp.count(hash) == 0) {
		mp[hash].push_back(strs[i]);
	    } else {
		if (mp[hash].size() == 1) ans.push_back(mp[hash][0]);
		mp[hash].push_back(strs[i]);
		ans.push_back(strs[i]);
	    }
	}
        return ans; 
    }

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
//8 check balanced tree
bool isBalancedHelper(TreeNode *root, int &h) 
{
    if (!root) {
	h = 0;
	return true;
    }
    int lh, rh;
    if (!isBalancedHelper(root->left, lh)) return false;
    if (!isBalancedHelper(root->right, rh)) return false;

    if (abs(lh - rh) > 1) return false;
    h = max(lh, rh) + 1;
    return true;
}

    bool isBalanced(TreeNode *root) {
        int h;
        return isBalancedHelper(root, h);
    }

//9 best time to buy sell stock
    int maxProfit(vector<int> &prices) {
	if (prices.size() < 2) return 0;
        int maxProfit = 0;
        int curMin = prices[0];
        for (int i = 1; i < prices.size(); i++) {
	    maxProfit = max(maxProfit, prices[i] - curMin);
	    curMin = min(curMin, prices[i]);
	} 
	return maxProfit;
    }

//buy sell stock 2. as many transaction as want
    int maxProfit2(vector<int> &prices) {
	if (prices.size() < 2) return 0;
        int maxProfit = 0;
	for (int i = 1; i < prices.size(); i++) {
	    if (prices[i] >= prices[i-1]) maxProfit += prices[i] - prices[i-1]; 
	}
	return maxProfit;
    }

//buy sell stock 3 at most 2 transaction
   int maxProfit3(vector<int> &prices) {
	if (prices.size() < 2) return 0;
        int maxProfit = 0;
        int curMin = prices[0];
	vector<int> dp1(prices.size(), 0), dp2(prices.size(), 0);

        for (int i = 1; i < prices.size(); i++) {
	    maxProfit = max(maxProfit, prices[i] - curMin);
	    dp1[i] = maxProfit;
	    curMin = min(curMin, prices[i]);
	} 

	maxProfit = 0;
	int curMax = prices[prices.size()-1];
	for (int i = prices.size()-2; i >= 0; i--) {
	    maxProfit = max(maxProfit, curMax - prices[i]);
	    dp2[i] = maxProfit;
	    curMax = max(curMax, prices[i]);
	}
	maxProfit = 0;
	for (int i = 0; i < prices.size(); i++)
	    maxProfit = max(maxProfit, dp1[i] + dp2[i]);

	return maxProfit;
        
    }

//Binary Tree inorder traverse
    vector<int> inorderTraversal(TreeNode *root) {
	vector<int> ans;
	stack<TreeNode *> stk;
	TreeNode *cur = root;
	while(!stk.empty() || cur) {
	    if (cur) {
		stk.push(cur);
		cur = cur->left;
	    } else {
		TreeNode *top = stk.top();	
		stk.pop();
		ans.push_back(top->val);
		cur = top->right;
	    }
	}
        return ans;
    }

//level order traverse
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > ans;
        queue<TreeNode *> que;
	//BUG
	if (!root) return ans;
	que.push(root);
	int curLevel = 1, nextLevel = 0;
	vector<int> tmp;
	while(!que.empty()) {
	    TreeNode *cur = que.front();
	    que.pop();
	    tmp.push_back(cur->val);
	    curLevel--;
	    if (cur->left) {
		que.push(cur->left);
		nextLevel++;
	    }
	    if (cur->right) {
		que.push(cur->right);
		nextLevel++;	
	    }	    
	    if (curLevel == 0) {
		ans.push_back(tmp);
		tmp.clear();
		curLevel = nextLevel;
		nextLevel = 0;
	    } 
	}
	return ans; 
    }

//zig-zag order traverse
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int> > ans;
        queue<TreeNode *> que;
	bool leftToRight = true;
	//BUG
	if (!root) return ans;
	que.push(root);
	int curLevel = 1, nextLevel = 0;
	vector<int> tmp;
	while(!que.empty()) {
	    TreeNode *cur = que.front();
	    que.pop();
	    tmp.push_back(cur->val);
	    curLevel--;
	    if (cur->left) {
		que.push(cur->left);
		nextLevel++;
	    }
	    if (cur->right) {
		que.push(cur->right);
		nextLevel++;	
	    }	    
	    if (curLevel == 0) {
		if (!leftToRight) reverse(tmp.begin(), tmp.end());
		ans.push_back(tmp);
		leftToRight = !leftToRight;
		tmp.clear();
		curLevel = nextLevel;
		nextLevel = 0;
	    } 
	}
	return ans; 
    }

//wildcard matching
//'?' Matches any single character.
//'*' Matches any sequence of characters (including the empty sequence).
    bool isMatch(const char *s, const char *p) {
	if (!*s && !*p) return true;
	else if (!*s) {
	    while(*p == '*') p++;
	    return *p == '\0';
	} else if (!*p) {
	    return false;
	}

	if (*p == '?') return isMatch(s+1, p+1);
	else if (*p == '*') {
	    int i = 0;
	    do {
		if (isMatch(s+i, p+1))
		    return true;
		i++;
	    } while(*(s+i));
	    //BUG here need to check when the s get to the end;
	    if (isMatch(s+i, p+1)) return true;
	} else {
	    return (*p == *s) && isMatch(s+1, p+1);
	}
	//BUG 
	return false;
    }

//regular expression matching
//'.' Matches any single character.
//'*' Matches zero or more of the preceding element.

    bool isMatch2(const char *s, const char *p) {
	return false;
    }

//climb stair
    int climbStairs(int n) {
	if (n <= 2) return n;
	int a = 1, b = 2;
	for (int i = 2; i < n; i++) {
	    int c = a + b;
	    a = b;
	    b = c;
	}
        return b; 
    }

//Combination Sum
    void dfs2(int index, vector<int> &candidates, int target, int sum, vector<int> &cur, vector<vector<int> > &ans)
    {
	//BUG: forget to add =
	if (index == candidates.size() || sum >= target) {
	    if (sum == target) 
		ans.push_back(cur);
	    return;
	}

	for (int i = index; i < candidates.size(); i++) {
	    cur.push_back(candidates[i]);
	    dfs2(i, candidates, target, sum+candidates[i], cur, ans);
	    cur.pop_back();
	}
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
	vector<vector<int> > ans;
	vector<int> cur;
	int sum = 0;
	sort(candidates.begin(), candidates.end());
	dfs2(0, candidates, target, sum, cur, ans);
        return ans;
    }

//Combination Sum II 2
    void dfs(int index, vector<int> &candidates, int target, int sum, vector<int> &cur, vector<vector<int> > &ans)
    {
	//BUG: forget to add =
	if (index == candidates.size() || sum >= target) {
	    if (sum == target) {
		ans.push_back(cur);
	    }
	    return;
	}

	for (int i = index; i < candidates.size(); i++) {
	    if (i != index && candidates[i] == candidates[i-1]) continue;
	    cur.push_back(candidates[i]);
	    dfs(i+1, candidates, target, sum+candidates[i], cur, ans);
	    cur.pop_back();
	}
    }

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
	vector<vector<int> > ans;
	vector<int> cur;
	int sum = 0;
	sort(num.begin(), num.end());
	dfs(0, num, target, sum, cur, ans);
        return ans;
    }

//combinations
    void dfs(int index, int n, int k, vector<int> &cur, vector<vector<int> > &ans)
    {
	if (index == n || cur.size() >= k) {
	    if (cur.size() == k) ans.push_back(cur);
	    return;
	}
	    cur.push_back(index+1);
	    dfs(index+1, n, k, cur, ans); 
	    cur.pop_back();
	    dfs(index+1, n, k, cur, ans);
    }

    vector<vector<int> > combine(int n, int k) {
	vector<vector<int> > ans;
	vector<int> cur;
	dfs(0, n, k, cur, ans);
	return ans;
    }

int inOrder[100];
int postOrder[100];

TreeNode *buildTreeHelper(int inOrder[], int len1, int postOrder[], int size2)
{
    //BUG
    if (len1 <= 0) return NULL;

    TreeNode *root = new TreeNode(postOrder[size2-1]);
    int index = 0;
    for (index = 0; index < len1; index++) {
	if (inOrder[index] == root->val) break;
    }
    root->left = buildTreeHelper(inOrder, index, postOrder, index);
    root->right = buildTreeHelper(inOrder+index+1, len1-index-1, postOrder+index, len1-index-1);
    return root;
}

//construct tree from inroder post order traverse
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
	for(int i = 0; i < inorder.size(); i++) 
	    inOrder[i] = inorder[i];

	for (int i = 0; i < postorder.size(); i++)
	    postOrder[i] = postorder[i];

        return buildTreeHelper(inOrder, inorder.size(), postOrder, postorder.size()); 
    }

//container with most water
    int maxArea(vector<int> &height) {
	int ans = 0;
	int i = 0, j = height.size()-1;
	while( i < j) {
	    //BUG do not need to -1
	    //ans = max(ans, min(height[i], height[j]) * (j-i-1));
	    ans = max(ans, min(height[i], height[j]) * (j-i));
	    if (height[i] <= height[j]) i++;
	    else j--;
	}
	return ans;
    }

//tree from array
TreeNode *sortedArrayHelper(vector<int> &num, int l, int r)
{
    if (l > r) return NULL;

    if (l == r) {
	return new TreeNode(num[l]);
    }

    int mid = l + (r-l)/2;
    TreeNode *root = new TreeNode(num[mid]);
    root->left = sortedArrayHelper(num, l, mid-1);
    root->right = sortedArrayHelper(num, mid+1, r);
    return root;
}
    TreeNode *sortedArrayToBST(vector<int> &num) {
	return sortedArrayHelper(num, 0, num.size() -1)	;
    }

//sorted list to tree
    int getLen(ListNode *root) {
	int ans = 0;
	while(root) {
	    ans++;
	    root = root->next;;
	}
	return ans;
    }
    TreeNode *sortedListToBSTHelper(ListNode *&head, int l, int r) {
	if (l > r) return NULL;

	int mid = l + (r-l)/2;
	TreeNode *left = sortedListToBSTHelper(head, l, mid-1);
        TreeNode *root = new TreeNode(head->val);
	head = head->next;	
	TreeNode *right = sortedListToBSTHelper(head, mid+1, r);
	root->right = right;
	root->left = left;
	return root;
    }

    TreeNode *sortedListToBST(ListNode *head) {
	ListNode *cur = head;
	int len = getLen(cur);
	return sortedListToBSTHelper(head, 0, len-1);
    }

//count and say
string getStr(const string &str)
{
    string ans;
    for (int i = 0; i < str.size(); ) {
	char ch = str[i];
	int cnt = 1;
	while(++i < str.size() && str[i] == ch) cnt++; 
	ans += cnt + '0';
	ans += ch;
    }
    return ans;
}
    string countAndSay(int n) {
	string str = "1";
	for (int i =1; i < n; i++)
	    str = getStr(str);
        return str;
    }

//decode ways full of BUG pass all test after fix. 
    int numDecodings(string s) {
	if (s.size() == 0 || s[0] == '0') return 0;
	vector<int> dp(s.size()+1, 0);
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 1; i < s.size(); i++) {
	    if (s[i] != '0') 
		dp[i+1] += dp[i];
	    if (s[i-1] != '0' &&  (10*(s[i-1] - '0') + (s[i] - '0') <= 26)) {
		dp[i+1] += dp[i-1];
	    }
	}
	return dp[s.size()];
    }

//divide two integers
    //a lot of BUG use long long as dividend may over flow.
    int divide(int dividend, int divisor) {
	bool isNeg = false;
	if (divisor == 1) return dividend;
	long long a = dividend, b = divisor;
	if (a< 0) {isNeg = !isNeg; a= -a;}
	if (b< 0) {isNeg = !isNeg; b = -b;} 
	
	int k = 0, ans = 0;
	//BUG add equal
	while(a >= (b<< k)) k++;
	k--;
	while(k > 0) {
	    //BUG add equal
	    if (a >= (b<< k)) {
		a -= (b<< k);
		ans |= (1 << k);
	    }
	    k--;
	}
	return isNeg ? -ans : ans;
    }

//edit distance
    int minDistance(string word1, string word2) {
	int len1 = word1.size(), len2 = word2.size();
	vector<vector<int> > dp(len1+1, vector<int>(len2+1, 0));

	for (int i = 0; i <= len1; i++) dp[i][0] = i;
	for (int i = 0; i <= len2; i++) dp[0][i] = i;

        for (int i = 1; i <= len1; i++) {
	    for (int j = 1; j <= len2; j++) {
		dp[i][j] = min(dp[i-1][j-1] + (word1[i-1] != word2[j-1]), 
				min(dp[i-1][j]+1, dp[i][j-1] + 1));
	    }
	} 
	return dp[len1][len2];
    }

//find missing positive
    //BUG
    int firstMissingPositive(int A[], int n) {
	for (int i = 0; i < n ;i++) {
	    if (A[i] <= 0 || A[i] > n) continue;
	    if(A[i] != i+1 && A[A[i]-1] != A[i]) {
		int tmp = A[A[i]-1];
		A[A[i]-1] = A[i];
		A[i] = tmp;
		i--;
	    }
	}
	for (int i = 0; i < n; i++) 
	    if (A[i] != i+1) return i+1;
	return n+1;
    }

//flattern binary tree to linklist
void flatterHelper(TreeNode *root, TreeNode *&pre)
{
    if (!root) return;
    pre->right = root;
    pre = pre->right;
    flatterHelper(root->left, pre);
    flatterHelper(root->right, pre);
}
    
        void flatten(TreeNode *root) {
	    TreeNode *head= new TreeNode(0);
	    TreeNode *pre = head;
	    flatterHelper(root, pre);
	    root = head->right;
	}
        
//generate paren
void dfs(int left, int right, const string &cur, vector<string> &ans)
{
    if (!left && !right) {
	ans.push_back(cur);
	return;
    }
    
    if (left > 0) dfs(left-1, right, cur + '(', ans);
    if (left < right) dfs(left, right-1, cur + ')', ans); 
}
    vector<string> generateParenthesis(int n) {
	vector<string> ans;
	string cur;
        dfs(n, n, cur, ans);
	return ans; 
    }

//strstr
    char *strStr(char *haystack, char *needle) {
	if (!haystack || !needle) return NULL;
	char *cur = haystack;
	while(*haystack) {
	    char *cur = haystack;
	    char *pDst = needle;
	    while(*cur && *pDst && *cur == *pDst) {
		cur++;
		pDst++;
	    }
	    if (!*pDst) return haystack;
	    haystack++;
	}
        return NULL; 
    }

  struct Interval {
      int start;
      int end;
      Interval() : start(0), end(0) {}
      Interval(int s, int e) : start(s), end(e) {}
  };

//BUG
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
	bool insert = false;
	
	vector<Interval> ans;
	for (int i = 0; i < intervals.size(); i++) {
	    //BUG again miss consideration [1,5] merge [2,3]
	  /*  if ((intervals[i].start >= newInterval.start&& intervals[i].start <= newInterval.end) ||
		 (intervals[i].end >= newInterval.start&& intervals[i].end <= newInterval.end)) { */
	    if (!(intervals[i].end < newInterval.start || (intervals[i].start > newInterval.end))) {
		newInterval.start = min(intervals[i].start, newInterval.start);
		newInterval.end = max(intervals[i].end, newInterval.end);
		continue;
	    }
	    //BUG again should detect inert or not
	    if (!insert && intervals[i].start >= newInterval.end) {
		ans.push_back(newInterval);
		insert = true;
	    } 
	    ans.push_back(intervals[i]);
	}
        if (!insert) 
	    ans.push_back(newInterval);
	return ans; 
    }

//integer to roman
    string intToRoman(int num) {
        map<int, string> mp;
        mp[1000] = "M";              
        mp[900] = "CM";              
        mp[500] = "D";              
        mp[400] = "CD";              
        mp[100] = "C";              
        mp[90] = "XC";              
        mp[50] = "L";              
        mp[40] = "XL";              
        mp[10] = "X";              
        mp[9] = "IX";              
        mp[5] = "V";              
        mp[4] = "IV";              
        mp[1] = "I";              
	string ans;
	for (map<int, string>::reverse_iterator iter = mp.rbegin(); iter != mp.rend(); iter++) {
	    while(num >= iter->first) {
		ans += iter->second;
		num -= iter->first;	
	    }
	}
	return ans;
    }

    int romanToInt(string s) {
        map<string, int> mp;
        mp["M"] = 1000;              
	mp["CM"] = 900;
	mp["D"] = 500;
	mp["CD"] = 400;
	mp["C"] = 100;
	mp["XC"] = 90;
	mp["L"] = 50;
	mp["XL"] = 40;
	mp["X"] = 10;
	mp["IX"] = 9;
	mp["V"] = 5;
	mp["IV"] = 4;
	mp["I"] = 1;
        int ans = 0;
	for (int i = 0; i < s.size(); ) {
	    if (i+1 < s.size() && mp.count(s.substr(i,2))) {ans += mp[s.substr(i,2)]; i += 2;}
	    else {ans += mp[s.substr(i,1)]; i += 1;}
	}
	return ans;
    }

//interleaving string
//BUG look at past answer
    int isInterleaveHeper(const string &s1, int id1, const string &s2, int id2, const string &s3, int id3, vector<vector<vector<int> > > &dp)
    {
	if (dp[id1][id2][id3] != -1) return dp[id1][id2][id3];
        if (id3 == s3.size()) return true;
        int result = 0;
        if (s1[id1] == s3[id3] && isInterleaveHeper(s1, id1+1, s2, id2, s3, id3+1, dp)) result = 1;
        if (!result && s2[id2] == s3[id3] && isInterleaveHeper(s1, id1, s2, id2+1, s3, id3+1, dp)) result = 1;
	dp[id1][id2][id3] = result;
	return result;
    }

    bool isInterleave(string s1, string s2, string s3) {
        vector<vector<vector<int> > > dp(s1.size()+1, vector<vector<int> >(s2.size()+1, vector<int>(s3.size()+1, -1)));        
        
        if (s1.size() + s2.size() != s3.size()) return false;
        return isInterleaveHeper(s1, 0, s2, 0, s3, 0, dp) == 1;      
    }

//jump game
//BUG a lot
    bool canJump(int A[], int n) {
        int cur = 0;
        while(cur < n) {
            int next = cur;
            int farest = cur;
            for (int i = 1; i <= A[cur]; i++) {
                if (farest < cur + i + A[cur+i]) {
                    farest = cur + i + A[cur+i];
                    next = cur + i;
                }   
            }   
            if (next >= n-1) return true;
            if (next <= cur) return false;
            cur = next;
        }   
        return true;    
    }   
//jumpe game 2 minimum steps
    int jump(int A[], int n) {
	int ans = 0;
        int cur = 0;
        while(cur < n-1) {
            int next = cur;
            int farest = cur;
            for (int i = 1; i <= A[cur]; i++) {
		//BUG fix this greeddy will have bug here
		if (cur + i >= n-1) return 1+ans;
                if (farest < cur + i + A[cur+i]) {
                    farest = cur + i + A[cur+i];
                    next = cur + i;
		    if (next >= n-1) return 1+ans;
                }   
            }   
	    ans++;
            if (next >= n-1) return ans;
            if (next <= cur) return 0;
            cur = next;
        }   
        return 0;    
    }   

//largest histogram
int cal(stack<int> &stk, const vector<int> &height, int right)
{
    int h = height[stk.top()];
    stk.pop();
    int left = stk.empty() ? -1 : stk.top();
    return (right - left - 1) * h;
}


    int largestRectangleArea(vector<int> &height) {
        stack<int> stk;	

	int maxArea = 0;
	for (int i = 0; i < height.size(); i++) {
	    if (stk.empty() || height[i] >= height[stk.top()]) stk.push(i);
	    while(!stk.empty() && height[i] < height[stk.top()]) {
		maxArea = max(maxArea, cal(stk, height, i));
	    }
	    stk.push(i);
	}
	while(!stk.empty()) 
	    maxArea = max(maxArea, cal(stk, height, height.size()));
        return maxArea; 
    }

//length of last word
    int lengthOfLastWord(const char *s) {
	int len = 0;
	while(*s) {
	    while(*s == ' ') s++;
	    //BUG need to check "b a  "
	    if (*s) len = 0;
	    while(*s != ' ' && *s != '\0') {s++; len++;}
	}
	return len;
    }

//letter combination of phone number
void dfs(int index, const string &digits, const string &cur, vector<string> &ans, string mp[10])
{
    if (index == digits.size()) {
	ans.push_back(cur);
	return;
    }
    
    for (int i = 0; i < mp[digits[index] - '0'].size(); i++) {
	dfs(index+1, digits, cur+mp[digits[index] - '0'][i], ans, mp);
    }
}
    vector<string> letterCombinations(string digits) {
        string mp[10] = {"", "", "abc", "def", "ghi", "jkl","mno","pqrs","tuv","wxyz"};
	vector<string> ans;
        dfs(0, digits, "", ans, mp); 
	return ans;
    }

//longest common prefix
    string longestCommonPrefix(vector<string> &strs) {	 
	string ans;
	int index = 0;
	//BUG need to check strs.size() first inroder to proceed.
	if (strs.size() == 0) return ans; 
	while(1) {
	    if (index == strs[0].size()) return ans; 
	    char cur = strs[0][index];
	    for (int i = 1; i < strs.size(); i++)  {
		if (index == strs[i].size() || cur != strs[i][index]) return ans;
	    }
	    ans += cur;
	    index++;
	}
	return ans;
    }


//reverse nodes in k group
ListNode*reverse(ListNode *head, ListNode *next)
{
    ListNode *pre = next;
    while(head->next != next) {
	ListNode *newNext = head->next;
	head->next = pre;
	pre = head;
	head = newNext;
    }
    head->next = pre;
    return head;
}
//a lot a lot of bugs
    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode *dummy = new ListNode(0);
	dummy->next = head;
	ListNode *cur = head, *preEnd = dummy, *next;

	while(1) {
	    next = cur;
	    for (int i = 0; i < k-1 && next; i++) next = next->next;
	    if (!next) break;	
	    ListNode *newNext = next->next;
	    preEnd->next = reverse(cur, next->next);
	    preEnd = cur;
	    cur = newNext;
	}
	return dummy->next;
    }

//longest palindrome substring
string expand(const string &s, int i, int j)
{
    string ans;
    while(i >= 0 && j <= s.size()-1 && s[i] == s[j]) {
	i--;
	j++;
    }
    return s.substr(i+1, j-i-1);
}

    string longestPalindrome(string s) {
	string ans = "";
	for (int i = 0; i < s.size(); i++) {
	    string str1 = expand(s, i, i);
	    if (ans.size() < str1.size()) ans = str1;
	    str1 = expand(s, i, i+1);
	    if (ans.size() < str1.size()) ans = str1;
	}
	return ans;
    }

//longest string without repeating 
//SO FALIL A LOF OF BUGS
    int lengthOfLongestSubstring(string s) { 
	//big bug need to init this hash
        bool hash[256] = {0};
        string ans; 
        int start = 0, maxLen = 0; 
      //  hash[s[0]] = true;
        int i = 0;
        for (i = 0; i < s.size(); i++) {
            if (!hash[s[i]]) {hash[s[i]] = true; continue;}
	    cout << i << " " << start << endl;
            maxLen = max(maxLen, i - start);
            while(s[start] != s[i]) {
		//big bug here 
                hash[s[start]] = false;
                start++;     
            }    
            start++;
        }    
	cout << start << " " << i << endl;
        maxLen = max(maxLen, i - start);
        return maxLen;
    }    

//maximum rectangele
//a lot of BUGS
    int maximalRectangle(vector<vector<char> > &matrix) {
	//bug check tiis
	if (matrix.size() == 0) return 0;
	vector<vector<int> > mat(matrix.size(), vector<int>(matrix[0].size(), 0));
	for (int j = 0; j < matrix[0].size(); j++) 
	    mat[0][j] = matrix[0][j] == '1';

	for (int i = 1; i < matrix.size(); i++) {
	    for (int j = 0; j < matrix[0].size(); j++) {
		mat[i][j] = matrix[i][j] == '1' ? mat[i-1][j] + 1 : 0; 
	    }
	}
	int maxArea = 0;
	for (int i = 0; i < matrix.size(); i++) {
	    maxArea = max(maxArea, largestRectangleArea(mat[i]));
	}
	return maxArea;
    }

//max depth of a tree
void maxHelper(TreeNode *root, int level, int &ans)
{
    if (!root->left && !root->right) {
	ans = max(level, ans);
	return;
    }
    if (root->left) maxHelper(root->left, level+1, ans);
    if (root->right) maxHelper(root->right, level+1, ans);
}

    int maxDepth(TreeNode *root) {
	if (!root) return 0;
        int ans = 0;
        maxHelper(root, 1, ans); 
        return ans;
    }

//maximum sub sum array
    int maxSubArray(int A[], int n) {
	//bug must init to INT_MIN to avoid all negaitve problem
        int maxSum = -100000;
        int sum = 0; 
	for (int i = 0; i < n; i++) {
	    sum += A[i];
	    maxSum = max(sum, maxSum);
	    if (sum < 0) sum = 0;
	}
	return maxSum; 
    }

//media of two sorted array
double findKth(int A[], int m, int B[], int n, int k)
{
    if (m > n) return findKth(B, n, A, m, k);
    //BUG very important
    if (m == 0) return B[k-1];
    if (k == 1) return min(A[0], B[0]);
    //BUG should not do this indexA is possible 0
   // int indexA = (m*k)/(m+n);
    int indexA = min(k/2, m);
    int indexB = k - indexA;
    if (A[indexA-1] < B[indexB-1]) {
	return findKth(A+indexA, m-indexA, B, n, k - indexA);
    } else {
	return findKth(A, m, B+indexB, n-indexB, k - indexB);
    }
}

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
	int sum = m+n;
	//BUG here should be old
	if (sum & 0x1) {
	    return findKth(A, m, B, n, (sum+1)/2);
	} else {
	    return (findKth(A, m, B, n, sum/2) + findKth(A,m, B, n, sum/2+1))/2;
	}
    }


//BUG wrong prototype
bool myComp(const Interval &lhs, const Interval &rhs)
//bool myComp(Interval lhs, Interval rhs)
{
    return lhs.start == rhs.start ? lhs.end< rhs.end: lhs.start < rhs.start;
}

    vector<Interval> merge(vector<Interval> &intervals) {
	vector<Interval> ans;
	if (intervals.size() == 0) return ans;
	sort(intervals.begin(), intervals.end(), myComp);
	int curStart = intervals[0].start, curEnd = intervals[0].end;
	for (int i = 1; i < intervals.size(); i++) {
	    if (intervals[i].start <= curEnd) {
		curEnd = max(curEnd, intervals[i].end);
	    } else {
		ans.push_back(Interval(curStart, curEnd));
		curStart = intervals[i].start ;
		curEnd = intervals[i].end;
	    }	
	}
	ans.push_back(Interval(curStart, curEnd));
	return ans;
    }

//merge k sorted list
typedef pair<int, int> PII;
    ListNode *mergeKLists(vector<ListNode *> &lists) {
	ListNode *dummy= new ListNode(0);;
	ListNode *head = dummy;
	priority_queue<PII, vector<PII>, greater<PII> > pq;
        for (int i = 0; i < lists.size(); i++) {
	    if (lists[i]) {
		pq.push(PII(lists[i]->val, i));
		lists[i] = lists[i]->next;
	    }
	} 
	while(!pq.empty()) {
	    PII top = pq.top();
	    pq.pop();
	    head->next = new ListNode(top.first);
	    //BUG 
	    head = head->next;
	    if (lists[top.second]) {
		pq.push(PII(lists[top.second]->val, top.second));
		lists[top.second] = lists[top.second]->next;
	    }
	}
	return dummy->next;
    }	

//merge two sorted array
//BUG shit
    void merge(int A[], int m, int B[], int n) {
	int index = m+n-1;
	int indexA = m-1, indexB = n-1;
	//BUG also need to add indexA >= 0 here
	while(indexA >= 0 && indexB >= 0) {
	    if (B[indexB] >= A[indexA]) A[index--] = B[indexB--];
	    else A[index--] = A[indexA--];
	}
	while(indexB >= 0) 
	    A[index--] = B[indexB--];
        return; 
    }

//merge two linklist 
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
	ListNode *dummy = new ListNode(0);
	ListNode *cur = dummy;
	while(l1 || l2) {
	    ListNode **merge;
	    if (!l1) merge = &l2;
	    else if (!l2) merge = &l1;
	    else if (l1->val < l2->val) merge = &l1;
	    else merge = &l2;
	    cur->next = *merge;
	    cur = cur->next;
	    *merge = (*merge)->next;
	}
	return dummy->next;
    }

//min depeth of tree
typedef pair<TreeNode *, int> PTI;

    int minDepth(TreeNode *root) {
        if (!root) return 0;
	int depeth = 1;
	queue<PTI> q;
	q.push(PTI(root, 1)); 
	while(!q.empty()) {
	    PTI top = q.front();
	    q.pop();
	    if (!top.first->left && !top.first->right) return top.second;
	    if (top.first->left) q.push(PTI(top.first->left, top.second+1));
	    if (top.first->right) q.push(PTI(top.first->right, top.second+1));
	}
    }

//min path sum
    int minPathSum(vector<vector<int> > &grid) {
	vector<vector<int> > dp(grid.size(), vector<int>(grid[0].size(), 0));
	dp[0][0] = grid[0][0];
	for (int i = 1; i < grid.size(); i++) {
	    dp[i][0] = dp[i-1][0] + grid[i][0];
	}
	for (int j =1; j < grid[0].size(); j++) 
	    dp[0][j] = dp[0][j-1] + grid[0][j];

	for (int i = 1; i < grid.size(); i++) {
	    for (int j = 1; j < grid[0].size(); j++) {
		dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
	    }
	}
	return dp[grid.size()-1][grid[0].size()-1];
    }

//minimum windows contain substring
    string minWindow(string S, string T) {
	string ans;
	int needToFind[256] = {0};
	int hashFind[256] = {0};
	int matchCount = 0;
	for (int i = 0; i < T.size(); i++)
	    needToFind[T[i]]++;
        int start = 0; 
	for (int i = 0; i < S.size(); i++) {
	    if (!needToFind[S[i]]) continue;
	    hashFind[S[i]]++;
	    if (hashFind[S[i]] <= needToFind[S[i]]) matchCount++; 
	    if (matchCount >= T.size())  {
		//BUG here is not lie this
		while(needToFind[S[start]] == 0 || hashFind[S[start]] > needToFind[S[start]]) {
		    hashFind[S[start]] --;
		    start++;
		}
		//BUG
		if (ans.size() == 0 || ans.size() >  i-start) ans = S.substr(start, i-start+1);
	    }
	} 
	return ans;
    }

//multiply string
//BUG
    string multiply(string num1, string num2) {
	string ans(num1.size() + num2.size(), '0');
	int carry = 0;
	for (int i = 0; i < num1.size(); i++) {
	    int a = num1[num1.size()-i-1] - '0';
	    carry = 0;
	    for (int j = 0; j < num2.size(); j++) {
		int b = num2[num2.size()-1-j] - '0';
		int res = a*b + carry + (ans[i+j] - '0');
		carry = res/10;
		res = res%10;
		ans[i+j] = res + '0';
	    }
	    ans[i + num2.size()] = carry + '0';
	}	
	string rtn;
	int i;
	for (i = ans.size()-1; i >= 0; i--) 
	    if (ans[i] != '0') break;
	//BUG at least need to return 0;
	//rtn = ans.substr(0, i+1);
	//reverse(rtn.begin(), rtn.end());
	while(i >= 0) rtn += ans[i--];
	return rtn; 
    }


void dfsQueen(int index, int n, vector<int> &colHash, vector<int> &diagHash, vector<int> &diagHash2, vector<string> cur, vector<vector<string> > &ans)
{
    if (index == n) {
	ans.push_back(cur);
	return;
    }

    for (int i = 0; i < n; i++) {
	if (colHash[i] || diagHash[index+i] || diagHash2[index-i + n-1]) continue;
	colHash[i] = 1;
	diagHash[index+i] = 1;
	diagHash2[index-i + n-1] = 1;
	cur[index][i] = 'Q';
	dfsQueen(index+1, n, colHash, diagHash, diagHash2, cur, ans);
	cur[index][i] = '.';
	colHash[i] = 0;
	diagHash[index+i] = 0;
	diagHash2[index-i + n-1] = 0;

    }
}

    vector<vector<string> > solveNQueens(int n) {
	vector<int> colHash(n, 0);
	vector<int> diagHash(2*n-1, 0);
	vector<int> diagHash2(2*n-1, 0);
	vector<vector<string> > ans;
	vector<string> cur(n, string(n, '.')); 
	dfsQueen(0, n, colHash, diagHash, diagHash2, cur, ans);
	return ans;
    }


//palindrome number
//a lot of BUGS
    bool isPalindrome(int x) {
        if (x < 0) return false;
	int rev = 0;
//BUG fix
	if (x < 10) return true;
	while(x > 0) {
	    rev = rev*10 + x%10;
	    x = x/10;
	    if (x == rev) 
		return true;
	    if (x >= 10 && rev == x/10) 
		return true;
	} 
	return false;
    }

//partition list
    ListNode *partition(ListNode *head, int x) {
        ListNode *front = new ListNode(0), *end = new ListNode(0); 
	ListNode *f = front, *e = end;	
	while(head) {
	    if (head->val < x) {front->next = head; front = front->next;}
	    else {end->next = head; end = end->next;}
	    head = head->next;
	}
	//BUG
	end->next = NULL;
	front->next = e->next;
	return f->next;
    }

//pical triangle
    vector<vector<int> > generate(int numRows) {
	vector<vector<int> > ans;
	//BUG check
	if (numRows == 0) return ans;

        vector<int> cur, next; 
	cur.push_back(1);
	ans.push_back(cur);	
	for (int i = 1; i < numRows; i++) {
	    next.push_back(1);
	    //BIG BUG
//	    for (int i = 1; i <= numRows-1; i++) 
//		next.push_back(cur[i-1]+cur[i]);
	    for (int j = 0; j < cur.size()-1; j++) 
		next.push_back(cur[j]+cur[j+1]);
	    next.push_back(1);
	    ans.push_back(next);
	    cur = next;
	    next.clear();
	}
	return ans;
    }

//kth row of piscal triangle
//a lot of BUGS
    vector<int> getRow(int rowIndex) {
        vector<int> ans; 
      //  if (rowIndex == 0) return ans; 
        ans.resize(rowIndex+1);
        ans[0] = 1;
        for (int i = 1; i <= rowIndex; i++) {
            int pre = ans[0];
            for (int j = 1; j <= i-1; j++) {
                int tmp = pre + ans[j];
                pre = ans[j];
                ans[j] = tmp; 
            }    
            ans[i] = 1; 
        }    
        return ans; 
    } 

//tree has path sum
//a lot of BUGS
bool hasPathSumHelper(int curSum, TreeNode *node, int target)
{
    if (!node->left && !node->right) {
	if (curSum + node->val == target) return true;
	else return false;
    }

    bool ans = false;
    if (node->left) ans |= hasPathSumHelper(curSum + node->val, node->left, target);
    // what a fucking BUG
    if (node->right && !ans) ans |= hasPathSumHelper(curSum + node->val, node->right, target);
    return ans;    
}

    bool hasPathSum(TreeNode *root, int sum) {
	if (!root) return sum == 0;
	return hasPathSumHelper(0, root, sum);
    }

//all path vector
void pathSumDfs(TreeNode *root, int sum, vector<int> cur, vector<vector<int> > &ans)
{
    if (!root) return;
    sum -= root->val;
    cur.push_back(root->val);
    if (!root->left && !root->right && sum == 0)  {
	ans.push_back(cur);
	return;
    }
    pathSumDfs(root->left, sum, cur, ans);
    pathSumDfs(root->right, sum, cur, ans); 
}

    vector<vector<int> > pathSum(TreeNode *root, int sum) {
	vector<vector<int> > ans;
	vector<int> cur;
        pathSumDfs(root, sum, cur, ans); 
	return ans;
    }

//permutation sequence
// a lot of bug
    string getPermutation(int n, int k) {
	string ans;
	vector<int> vec;
	k = k-1;
	vector<int> hash(n+1, 0);
	for (int i = 0; i < n; i++) 
	    vec.push_back(i+1);

	int cur = 1;	
	for (int i = 1; i < n; i++) {
	    cur *= i;
	    hash[i] = cur;
	}
   
	while(vec.size() > 0) {
	    int index = vec.size() ==1 ? 0 : k/hash[vec.size()-1];
	    k = k%hash[vec.size()-1];
	    ans += vec[index]+ '0';
	    vec.erase(vec.begin() + index);
	} 
//	ans += vec[0] + '0';
	return ans;
    }

//permutations
void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void dfsPermu(int index, vector<int> &num, vector<int> &cur, vector<vector<int> > &ans)
{
    if (index == num.size()) {
	ans.push_back(cur);
	return;
    }
    for (int i = index; i < num.size(); i++) {
	cur.push_back(num[i]);
	swap(num[index], num[i]);
	dfsPermu(index+1, num, cur, ans);
	cur.pop_back();
	swap(num[index], num[i]);
    }
}

    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > ans;
	if (num.size() == 0) return ans;
	sort(num.begin(), num.end());
	vector<int> cur;
	dfsPermu(0, num, cur, ans);
	return ans; 
    }

//permute unique
void dfsPermuUnique(int index, vector<int> &num, vector<int> &cur, vector<vector<int> > &ans)
{
    if (index == num.size()) {
	ans.push_back(cur);
	for (int i = 0; i < cur.size(); i++) 
	    cout << cur[i] << " ";
	cout << endl;
	return;
    }
    for (int i = index; i < num.size(); i++) {
	if (i != index && num[i] == num[i-1]) continue;
	cur.push_back(num[i]);
	swap(num[index], num[i]);
	dfsPermuUnique(index+1, num, cur, ans);
	cur.pop_back();
	swap(num[index], num[i]);
    }
}

    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > ans;
	if (num.size() == 0) return ans;
	sort(num.begin(), num.end());
	vector<int> cur;
	dfsPermuUnique(0, num, cur, ans);
	return ans; 
        
    }

//plus one
    vector<int> plusOne(vector<int> &digits) {
	vector<int> ans;
	int carry = 1;
	for (int i = digits.size()-1; i>= 0; i--) {
	    int sum = digits[i] + carry;
	    carry = sum/10;
	    sum = sum%10;
	    ans.push_back(sum);
	}
	if (carry) ans.push_back(1);
	reverse(ans.begin(), ans.end());
	return ans;
    }

//populate each right pointer 
  struct TreeLinkNode {
   int val;
   TreeLinkNode *left, *right, *next;
   TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
  };
//allow extra memory solution
    void connect2(TreeLinkNode *root) {
	if (!root) return;
	queue<TreeLinkNode *> q;
	q.push(root);
	int curLevel = 1, nextLevel = 0;
	while(!q.empty()) {
	    TreeLinkNode* top = q.front();
	    q.pop();
	    curLevel--;
	    if (curLevel == 0) top->next = NULL;
	    else top->next = q.front();
	    if (top->left) {
		q.push(top->left);
		nextLevel++;
	    }
	    if (top->right) {
		q.push(top->right);
		nextLevel++;
	    }
	    if (curLevel == 0) {
		curLevel = nextLevel;
		nextLevel = 0;
	    }
	}
    }

    void connect(TreeLinkNode *root) {
	if (!root) return;
	TreeLinkNode *dummy = new TreeLinkNode(0);
//	root->next = NULL;
	TreeLinkNode *cur = NULL;;       
	while(root) {
	//BUGS
	//while(root || cur) {
	    cur = dummy;
//	    cur->next = NULL;
	    while (root) {
		if (root->left) {
		    cur->next = root->left;
		    cur = cur->next;
		}
		if (root->right) {
		    cur->next = root->right;
		    cur = cur->next;
		}
		root = root->next;
	    }  
	    cur->next = NULL;
	    root = dummy->next;
	}
    }

//pow
//a lot of BUGS
    double mypow(double x, int n) {
	if (n < 0) return 1/pow(x, -n);
	double ans = 1;
        double cur = x; 

	while(n > 0) {
	    if (n&1) {
		ans *= cur;
	    }
	    n = n >>1;
	    //what a fucking bug
	    cur *= cur;
	   // cur *= x;
	}

	return ans;
    }

//remove duplicate from sorted array
    int removeDuplicates(int A[], int n) {
        int index = 0;
	for (int i = 0; i < n; ) {
	    int cur = A[i];
	    A[index++] = cur;
	    while(++i < n && A[i] == cur) ;
	}
	return index;
    }

//remove duplicate 2
    int removeDuplicates2(int A[], int n) {
        int index = 0;
	for (int i = 0; i < n; ) {
	    int cur = A[i];
	    int cnt = 1;
	    A[index++] = cur;
	    while(++i < n && A[i] == cur) {
		if (cnt == 1) { cnt++; A[index++] = cur;}
	    } 
	}
	return index;
    }

//remove duplicated from sorted list
    ListNode *deleteDuplicates(ListNode *head) {
	ListNode *dummy = new ListNode(0);;
	ListNode *cur = dummy;
	while(head) {
	    int tmp = head->val;
	    cur->next = head; 
	    cur = cur->next;
	    while(head && head->val == tmp) {head = head->next;}
	}	
        cur->next = NULL;
	return dummy->next; 
    }

//remove duplicated from sorted list leaving only distainct
    ListNode *deleteDuplicates2(ListNode *head) {
	ListNode *dummy = new ListNode(0);;
	ListNode *cur = dummy;
	while(head) {
	    int tmp = head->val;
	    int cnt = 0;
	    //BUG save the previous pointer
	    cur->next = head;
	    while(head && head->val == tmp) {head = head->next; cnt++;}
	    if (cnt > 1) continue;
	    cur = cur->next;
	}	
        cur->next = NULL;
	return dummy->next; 
    }

//remove element in place
    int removeElement(int A[], int n, int elem) {
       int index = 0;
	for (int i = 0; i < n; i++) {
	    if (A[i] != elem) A[index++] = A[i];
	} 
	return index;
    }

//remove nth node from linklist
    ListNode *removeNthFromEnd(ListNode *head, int n) {
	ListNode *dummy = new ListNode(0);
	dummy->next = head;
	ListNode *fast = dummy, *slow = dummy;
	for (int i = 0; i < n && fast; i++) fast = fast->next;
	if (!fast) return head;
	while(fast) {
	    fast = fast->next;
	    slow = slow->next;
	}
	slow->next = slow->next->next;
    }

//resotre ip address
void dfsIp(int index, const string &s, vector<string> &cur, vector<string> &ans)
{
    if (index == s.size()) {
	if (cur.size() == 4) {
	    string str = cur[0] + '.' + cur[1] + '.' + cur[2] + '.' + cur[3];
	    ans.push_back(str);
	}
	return;
    }

    if (cur.size() >= 4) return;
    int val = 0;
    for (int i = index; i < s.size() && i < index+3; i++) {
        val = val*10 + s[i] - '0'; 
	if (val > 255 || (i!= index && s[index] == '0')) continue;
	cur.push_back(s.substr(index, i-index+1));
	dfsIp(i+1, s, cur, ans);
	cur.pop_back();
    }
}

    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
	vector<string> cur;
	dfsIp(0, s, cur, ans);
	return ans;
    }

//reverse the integer
    int reverse(int x) {
	int neg = x < 0 ? -1: 1;
	if (x == 0) return 0;
	x = abs(x);
	long long ans = 0;
	while(x > 0) {
	    ans = ans*10 + x%10;
	    x = x/10;
	} 
	return  neg*ans;
    }

//reverse integer
ListNode *reverse2(ListNode *head, ListNode *nt)
{
    ListNode *pre = nt, *cur = head;
    while(cur != nt) {
        ListNode *next = cur->next;
        cur->next = pre;
	pre = cur;
	cur = next;
    }
    return pre;
}

    ListNode *reverseBetween(ListNode *head, int m, int n) {
	ListNode *dummy = new ListNode(0);
	dummy->next = head;
	ListNode *from = dummy, *to = dummy;
        m -= 1;
	while(m-- > 0) from = from->next; 
	while(n-- > 0) to = to->next;
	from->next = reverse2(from->next, to->next);
	return dummy->next;
    }

//rotate image
    void rotate(vector<vector<int> > &matrix) {
        for (int i = 0; i < matrix.size(); i++) {
	    for (int j = 0; j < matrix[0].size(); j++) {
		int tmp = matrix[i][j];
		matrix[i][j] = matrix[j][i];
		matrix[j][i] = tmp;
	    } 
	} 
	for (int i = 0; i < matrix.size(); i++) {
	    int k = 0, l = matrix[0].size()-1;
	    while(k < l) {
		int tmp = matrix[i][k];
		matrix[i][k] = matrix[i][l];
		matrix[i][l] = tmp;
	    }
	}
    }

//rotate list
//a lot of BUGS
    ListNode *rotateRight(ListNode *head, int k) { 
        if (!head) return head;
        ListNode *fastPre= NULL, *fast = head, *slowPre = NULL,*slow = head;
        if (k == 0) return head;
        int len = getLen(head);
        k %= len;
        if (k == 0) return head;
        while(slow && k-- > 0) slow = slow->next;
        if (!slow) return head;
        while(slow) {
            fastPre = fast;
            fast = fast->next;
            slowPre = slow;
            slow = slow->next;
        }     
        slowPre->next = head;    
        fastPre->next = NULL;
        return fast;
    }  


//is same tree
bool isSameHelper(TreeNode *p, TreeNode *q)
{
    if (!p && !q) return true;
    if (!p || !q) return false;
    if (p->val != q->val) return false;
    return isSameHelper(p->left, q->left) && isSameHelper(p->right, q->right);
}
    bool isSameTree(TreeNode *p, TreeNode *q) {
        return isSameHelper(p, q);
    }


//search in 2D matrix
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
	int row = 0, col = matrix[0].size()-1;
	while(row < matrix.size() && col >= 0) {
	    if (matrix[row][col] > target) {
		col--;
	    } else if (matrix[row][col] == target) {
		return true;
	    } else {
		row++;
	    }
	}
	return false;
    }

//search range iteative
//add the best code
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> ans;
        ans.push_back(-1);
        ans.push_back(-1);
        int start = -1, end = -1;
        int lo = 0, hi = n-1; 
        while(lo <= hi) {
            int mid = lo + (hi-lo)/2;
            if ((mid == 0 || A[mid-1] < A[mid]) && A[mid] == target) {
                start = mid; 
                break;
            } else if (A[mid] >= target) {
                hi = mid-1; 
            } else if (A[mid] < target) {
                lo = mid+1;
            }    
        }    
        if (start == -1) return ans; 

        lo = 0; 
        hi = n-1; 
        while(lo <= hi) {
            int mid = lo + (hi-lo)/2;
            if ((mid == n-1 || A[mid] < A[mid+1]) && A[mid] == target) {
                end = mid; 
                break;
            } else if (A[mid] > target) {
                hi = mid-1;
            } else if (A[mid] <= target) {
                lo = mid+1;
            }    
        }    

        if (end == -1) return ans; 
        ans[0] = start;
        ans[1] = end;     
        return ans; 
    }   

//search in rotate sorted array
//BUG did not consider only one element
//BUG2 A[lo] should be <= target and target should be <= A[hi]
    int search(int A[], int n, int target) {
	int lo = 0, hi = n-1;
	while(lo <= hi) {
	    int mid = lo + (hi-lo)/2;
	    if (A[mid] == target) return mid;
	    else if (A[lo] <= A[mid]) {
		if (A[lo] <= target && target < A[mid]) hi = mid-1;
		else lo = mid+1;
	    } else if (A[mid] <= A[hi]) {
		if (A[mid] < target && target <= A[hi]) lo = mid+1;
		else hi = mid-1;
	    }
	}
	return -1;        
    }

//find search position
    int searchInsert(int A[], int n, int target) {
	int lo = 0, hi = n-1;
	if (target < A[0]) return 0;
	if (target > A[n-1]) return n;
	while(lo <= hi) {
	   int mid = lo + (hi-lo)/2;
	    if (A[mid] == target) return mid;
	    else if (A[mid] < target) lo = mid+1;
	    else hi = mid-1; 
	}
	if (A[lo] > target) return lo;
	else if (A[lo] < target) return  lo+1;
        
    }

//set matrix zeros
    void setZeroes(vector<vector<int> > &matrix) {
	int cnt = 0;
	for (int i = 0; i < matrix.size(); i++) 
	    if (matrix[i][0] == 0) {cnt=3; break;}
	for (int i = 0; i < matrix[0].size(); i++) 
	    if (matrix[0][i] == 0) {cnt++; break;}

	//fucking BUG again	
	for (int i = 1; i < matrix.size(); i++) {
	  //  if (matrix[i][0] == 0) continue;
	    for (int j = 1; j < matrix[0].size(); j++) {
	//	if (matrix[0][j] == 0) continue;
		if (matrix[i][j] == 0) {
		    matrix[i][0] = 0;
		    matrix[0][j] = 0;
//		    break;
		}	
	    }
	}

	//what a fucking bug here again. shopuld set the other col and row first.
        for (int i = 1; i < matrix.size(); i++) {
	    for (int j = 1; j < matrix[0].size(); j++) {
		if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
	    }
	} 

	//what a fucking BUG pig idea
	if (cnt >= 3)
	for (int i = 0; i < matrix.size(); i++) {
	    matrix[i][0] = 0;	
	}
	if (cnt == 1 || cnt == 4) 
	for (int i = 0; i < matrix[0].size(); i++) {
	    matrix[0][i] = 0;	
	}
	
    }

//simple path
//so many FUCKING BUGS shit
/*    string simplifyPath(string path) {
	stack<string> stk;
	for (int i = 0; i < path.size(); ) {
	    while(path[i] == '/') i++;
	    string str;
	    while(++i < path.size() && path[i] != '/') str += path[i];
	    if (str == ".") continue;
	    else if (str == "..") {if (!stk.empty()) stk.pop(); continue;}
	    else stk.push(str);
	}        
	string ans;
	while(!stk.empty()) {
	    ans = ans + '/' + stk.top();
	    stk.pop();
	}
	return ans;
    } */

    string simplifyPath(string path) {
        stack<string> stk; 
        
        for (int i = 0; i < path.size(); ) {
            while(path[i] == '/') i++; 
            string str; 
            while(i < path.size() && path[i] != '/') {str += path[i]; i++;}
	    //just forget about the str.size() is 0 case
            if (str == "." || str.size() == 0) continue;
            else if (str == "..") {if (!stk.empty()) stk.pop(); continue;}
	    //BUG forget to think about go to end and get '/'
	    else if (str == "/") continue;
            else stk.push(str);
        }     
        string ans; 
        while(!stk.empty()) {
	    cout << stk.top() << endl;
            ans = '/' + stk.top() + ans;
            stk.pop();
        }    
        if (ans.size() == 0) ans = "/";
        return ans; 
    }  

//sort colors
void swapColor(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}


//BUG could not even [1]
    void sortColors(int A[], int n) {
	int i = -1, j = 0, k = n;
	for (j = 0; j < k; j++) {
	    cout << A[j] << endl;
	    if (A[j] == 0) {
		swap(A[++i], A[j]);
		//what a fucking BUG, this does not need to go back
		//j--;
	    } else if (A[j] == 1) {
		continue;
	    } else {
		swap(A[--k], A[j]);
		j--;
	    }
	}
    }

//spirial matrix
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
	vector<int> ans;
	if (matrix.size() == 0) return ans;
        int l = 0, r = matrix[0].size()-1, u = 0, d = matrix.size()-1; 
	//waht a BUG should be l <= r && u <= d
	//forget to consider the l == r and u == d case
	while(l <= r && u <= d) {
	    for (int i = l; i <= r; i++) {
		ans.push_back(matrix[u][i]);
	    }
	    for (int i = u+1; i <= d; i++) 
		ans.push_back(matrix[i][r]);
	    if (u != d) 
	    for (int i = r-1; i >= l; i--) 
		ans.push_back(matrix[d][i]);

	    if (l != r)
	    for (int i = d-1; i > u; i--)
		ans.push_back(matrix[i][l]);
	    l++;
	    r--;
	    u++;
	    d--;	
	}
	return ans;
    }


//generate spirial matrix
    vector<vector<int> > generateMatrix(int n) {
	vector<vector<int> > matrix(n, vector<int>(n, 0));
	if (n == 0) return matrix;
	int index = 1;
        int l = 0, r = matrix[0].size()-1, u = 0, d = matrix.size()-1; 
	//waht a BUG should be l <= r && u <= d
	//forget to consider the l == r and u == d case
	while(l <= r && u <= d) {
	    for (int i = l; i <= r; i++) {
		matrix[u][i] = index++;;
	    }
	    for (int i = u+1; i <= d; i++) 
		matrix[i][r] = index++;

	    for (int i = r-1; i >= l && u != d ; i--) 
		matrix[d][i] = index++;

	    for (int i = d-1; i > u && l != r; i--)
		matrix[i][l] = index++;
	    l++;
	    r--;
	    u++;
	    d--;	
	}
	return matrix;
    }

//sqrt
#define EPS 0.00001
    int sqrt(int x) {
	if (x <= 0) return 0;
	if (x == 1) return 1;
	int lo, hi, mid;
	if (x < 1) {lo = x; hi = 1;}
	if (x > 1) {lo = 1; hi = x;}
	while(lo <= hi) {
	    mid = lo + (hi-lo)/2;
	    if (mid == x/mid) return mid;
	    else if (mid < x/mid) lo = mid+1;
	    else hi = mid -1; 
	} 
	if (mid  < x/mid) return mid;
	else return mid-1; 
    }

//atoi
    int atoi(const char *str) {
        bool isNeg = false;
	long long ans = 0;
	while(*str == ' ') str++;
	if (*str == '+') str++;
	else if (*str == '-') {str++; isNeg = true;}
	while(*str >= '0' && *str <= '9') {
	    ans = ans*10 + (*str - '0');
	    str++;
	    if ((!isNeg && ans > INT_MAX) || (isNeg && -ans < INT_MIN)) return isNeg ? INT_MIN : INT_MAX;
	}
	return isNeg ? -ans : ans;
    }

//subset
void dfs(int index, vector<int> &s, vector<int> &cur, vector<vector<int> > &ans)
{
    if (index == s.size()) {
	ans.push_back(cur);
	return;
    }
   //fuck whare am i doing such a stupid bug
 //   for (int i = index; i < s.size(); i++) {
	cur.push_back(s[index]);
	dfs(index+1, s, cur, ans);
	cur.pop_back();
	dfs(index+1, s, cur, ans);
  //  }
}

    vector<vector<int> > subsets(vector<int> &S) {
	sort(S.begin(), S.end());
        vector<vector<int> > ans;
	vector<int> cur;
	dfs(0, S, cur, ans);
	return ans;
    }
//subset 2
//subset
void dfs2(int index, vector<int> &s, vector<int> &cur, vector<vector<int> > &ans)
{
    if (index == s.size()) {
        ans.push_back(cur);
        return;
    }    
   //fuck whare am i doing such a stupid bug
 //   for (int i = index; i < s.size(); i++) {
        cur.push_back(s[index]);
        dfs(index+1, s, cur, ans);
        cur.pop_back();
        dfs(index+1, s, cur, ans);
  //  }  
}

    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > ans; 
        vector<int> cur; 
        dfs(0, S, cur, ans);
        return ans; 
    } 

//sudoku
typedef pair<int, int> PII;

bool Valid(vector<vector<char> > &board)
{
    int hash[9] = {0};
    for (int i = 0; i < 9; i++) {
        memset(hash, 0, sizeof(hash));
	for (int j = 0; j < 9; j++) {
	    if (board[i][j] == '.') continue;
	    hash[board[i][j] - '1']++;
	    if (hash[board[i][j] - '1'] > 1) return false;
	}
    }

    for (int j = 0; j < 9; j++) {
        memset(hash, 0, sizeof(hash));
	for (int i = 0; i < 9; i++) {
	    if (board[i][j] == '.') continue;
	    hash[board[i][j] - '1']++;
	    if (hash[board[i][j] - '1'] > 1) return false;
	}
    }

    for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	    memset(hash, 0, sizeof(hash));
	    for (int k = 0; k < 3; k++) {
		for (int l = 0; l < 3; l++) {
		    if (board[i*3+k][3*j+l] == '.') continue;
		    hash[board[i*3+k][3*j+l]]++;
		    if (hash[board[i*3+k][3*j+l]] > 1) return false;
		} 
	    }
	}
    }
    return true;
}

PII findCell(vector<vector<char> > &board)
{
    for (int i = 0; i < 9; i++) {
	for (int j = 0; j < 9; j++) {
	    if (board[i][j] == '.') return make_pair(i, j);
	}
    }
    return make_pair(-1, -1);
}

bool solveSudokuHelper(vector<vector<char> > &board) {
	    PII point = findCell(board);
	    if (point.first == -1) return true;
	    for (int i = 1; i <= 9; i++) {
		board[point.first][point.second] = i+'0';
		if (Valid(board) && solveSudokuHelper(board)) return true;
	    } 
    return false;
}

    void solveSudoku(vector<vector<char> > &board) {
	solveSudokuHelper(board);    
    }


//swap nodes in pair
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy = new ListNode(0);
	dummy->next = head;
	ListNode *cur = head, *pre = dummy;
	while(cur) {
	    if (!cur->next) break;;
	    ListNode *next = cur->next->next;
	    pre->next = cur->next;
	    cur->next->next = cur;
	    cur->next = next;
	    pre = cur;
	    cur = next;
	}
	return dummy->next;
    }


//symmertric tree
bool isSymmetricHelper(TreeNode *left, TreeNode *right)
{
    if (!left && !right) return true;
    if (!left || !right) return false;
    return left->val== right->val&& isSymmetricHelper(left->right, right->left) && isSymmetricHelper(left->left, right->right);

}

    bool isSymmetric(TreeNode *root) {
	if (!root) return true;
	return isSymmetricHelper(root->left, root->right);
    }

//trapping rain water
    int trap(int A[], int n) {
	int maxIndex = 0;
	for (int i = 1; i < n; i++) 
	    if (A[i] > A[maxIndex]) maxIndex = i;

	int area = 0;
	int curMax = A[0];
	for (int i = 1; i < maxIndex; i++) {
	    if (A[i] < curMax) area += curMax - A[i];
	    else curMax = A[i]; 
	}
	curMax = A[n-1];
	for (int i = n-2; i > maxIndex; i--) 
	    if (A[i] < curMax) area += curMax - A[i];
	    else curMax = A[i];

       return area; 
    }

//shit a log of bugs.
    int minimumTotal(vector<vector<int> > &triangle) {
        int ans = 10000000;
        if (triangle.size() == 1) return triangle[0][0];
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle[i].size(); j++) {
                int left = j == 0 ? 100000: triangle[i-1][j-1];
                int right = j == triangle[i-1].size() ? 100000: triangle[i-1][j];
//		cout << i << " " << j << " " << left << " " << right << " " << triangle[i][j] << endl;
                triangle[i][j] = min(left + triangle[i][j], right + triangle[i][j]);
//		cout << i << " " << j << " " << left << " " << right << " " << triangle[i][j] << endl;
//	    cout << triangle[i][j] << " ";
            }    
//	    cout << endl;
        }
        for (int j = 0; j < triangle[triangle.size()-1].size(); j++)
            ans = min(ans, triangle[triangle.size()-1][j]);
        
        return ans; 
    }

//two sum
    vector<int> twoSum(vector<int> &numbers, int target) {
	map<int, int> mp;
	vector<int> ans;
	for (int i = 0; i < numbers.size() ;i++)
	    if (mp.count(target - numbers[i]) != 0) {
		//what a fucking BUG, come on man, it should be mp[target - numbers[i]]
		ans.push_back(mp[numbers[i]]);
		ans.push_back(i);
		return ans;
	    } else {
		mp[numbers[i]] = i;
	    }
	return ans;
    }

//number of unique binary search tree
//what a fucking BUG in the loop need to be <= n
    map<int, int> treeMap;
    int numTrees(int n) {
	if (n == 0 || n == 1) return 1;
	if (treeMap.count(n)) return treeMap[n];
	int count = 0;
	for (int i = 1; i <= n; i++) {
	    int left = numTrees(i-1);
	    int right = numTrees(n-i);
	    count += left*right;
	}	
        return treeMap[n] = count; 
    }

//unique path
    int uniquePaths(int m, int n) {
	vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
	dp[1][1] = 1;
        for (int i = 1; i <= m; i++) {
	    for (int j = 1; j <= n; j++)  {
		if (i == 1 && j == 1) continue;
		dp[i][j] = dp[i-1][j] + dp[i][j-1];
	    }
	} 
	return dp[m][n];
    }

//obstacle
    int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
	if (obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0) return 0;
	if (obstacleGrid[0][0] == 1) return 0;

	int m = obstacleGrid.size(), n = obstacleGrid[0].size();
	vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
	dp[1][1] = 1;
        for (int i = 1; i <= m; i++) {
	    for (int j = 1; j <= n; j++)  {
		if (i == 1 && j == 1) continue;
		if (obstacleGrid[i-1][j-1] == 1) continue;
		else dp[i][j] = dp[i-1][j] + dp[i][j-1];
	    }
	} 
	return dp[m][n];
        
    }

//valid paren
//what a fucking BUG, should be this stk.empty() ||
    bool isValid(string s) {
	stack<char> stk;
	for (int i = 0; i < s.size(); i++) {
	    if (s[i] ==	')') {
	        if (!stk.empty() && stk.top() != '(') return false; 
		stk.pop();
	    } else if (s[i] == ']') {
	        if (!stk.empty() && stk.top() != '[') return false; 
		stk.pop();
	    } else if (s[i] == '}') {
	        if (!stk.empty() && stk.top() != '{') return false; 
		stk.pop();
	    } else {
		stk.push(s[i]);
	    }
	}
        return stk.size() == 0;
    }

    bool isValid2(string s) { 
        stack<char> stk; 
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ')') {
                if (stk.empty() || stk.top() != '(') return false; 
                stk.pop();
            } else if (s[i] == ']') {
                if (stk.empty() || stk.top() != '[') return false; 
                stk.pop();
            } else if (s[i] == '}') {
                if (stk.empty() || stk.top() != '{') return false; 
                stk.pop();
            } else {
                stk.push(s[i]);
            }    
        }    
        return stk.size() == 0;
    }  


bool isValidBSTHelper(TreeNode *root, int lo, int hi)
{
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return isValidBSTHelper(root->left, lo, root->val) && 
	    isValidBSTHelper(root->right, root->val, hi);
}

    bool isValidBST(TreeNode *root) {
	if (!root) return true;
	return isValidBSTHelper(root, INT_MIN, INT_MAX);
    }


int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool matchHelper(vector<vector<char> > &board, int i, int j, const char *str, bool visited[50][50])
{
    if (!*str) return true;

    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j]) return false;

    if (board[i][j] != *str) return false;
    visited[i][j] = true;
   

//what the fucking bug are you doing. 
    for (int k = 0; k < 4; k++) 
        if (matchHelper(board, i + dx[k], j + dy[k], str+1, visited)) return true;
    visited[i][j] = false;
//fucking bug again
    return false;
} 

    bool exist(vector<vector<char> > &board, string word) {
	bool visited[50][50] = {false};
        for (int i = 0; i < board.size(); i++) {
	    for (int j = 0; j < board[0].size(); j++) 
		if (matchHelper(board, i, j, word.c_str(), visited)) return true;
	}    
    }



int main(int argc, char **argv)
{
    vector<int> nums;
    vector<vector<int> > matrix;
    nums.push_back(-1);
    matrix.push_back(nums);
    nums.clear();
    nums.push_back(2);
    nums.push_back(3);
    matrix.push_back(nums);
    nums.clear();
    nums.push_back(1);
    nums.push_back(-1);
    nums.push_back(-3);
    matrix.push_back(nums);
    nums.clear();
    cout << minimumTotal(matrix);
}
